package roman.algorithm;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class UnionFind {
	List<Node> nodeList = new ArrayList<Node>();
	Map<Integer,Integer> sizeMap = new HashMap<Integer,Integer>();
	
	class Node{
		int setName;
		Node parent;					// nodes with parent null is the name of the set
		public Node(int n, Node p){
			setName = n;
			parent = p;
		}
	}
	
	public UnionFind(int length){
		for(int i=0; i<length; i++){
			nodeList.add(new Node(i,null));
			sizeMap.put(i, 1);
		}
	}
	
	public int find(int i){
		
		if(nodeList.get(i).parent == null)
			return i;
		else{
			int tmp = find(nodeList.get(i).parent.setName);
			nodeList.get(i).parent = nodeList.get(tmp);
			return tmp;
		}
	}
	
	public void union(int a, int b){
		int tmpSize = sizeMap.get(a) + sizeMap.get(b);
		if(sizeMap.get(a)>sizeMap.get(b)){
			sizeMap.put(a, tmpSize);
			sizeMap.remove(b);
			nodeList.get(b).parent = nodeList.get(a);
		}
		else{
			sizeMap.put(b, tmpSize);
			sizeMap.remove(a);
			nodeList.get(a).parent = nodeList.get(b);
		}
	}
}